package arithmetic1.hashTable;

/*
    数组和链表实现哈希表用作缓存
    要求：一个公司每来一个员工都要把员工的id姓名记录下来，不允许使用数据库，速度越快越好
 */
//哈希表
public class HashTable {
    //定义一个链表数组,用来存储数据
    public EmpList[] empLists;
    //定义链表的个数
    public int size;

    public HashTable(int size){
        this.size=size;
        //创建size大小的链表数组
        empLists=new EmpList[size];
        //创建size个链表
        for(int i=0;i<size;i++){
            empLists[i]=new EmpList();
        }
    }

    //定义哈希散列函数
    public int hashValue(int id){
        return id%size;
    }

    //添加员工
    public void add(Emp emp){
        //得到该员工的哈希值
        int hashValue=hashValue(emp.id);
        //将该员工添加到对应的链表上面
        empLists[hashValue].add(emp);
    }

    //查找一个员工(找到了返回这个员工，没有找打就返回null)
    public Emp findById(int id){
        //得到哈希值
        int hashValue=hashValue(id);
        Emp emp = empLists[hashValue].findById(id);
        return emp;
    }

    //删除一个员工
    public void removeById(int id){
        int hashValue=hashValue(id);
        empLists[hashValue].removeById(id);
    }

    //打印哈希表
    public void print(){
        for(int i=0;i<size;i++){
            empLists[i].print(i+1);
        }
    }

}

//存储员工的单链表,没有头节点
class EmpList{
    //头结点
    public Emp head;

    public EmpList() {
        this.head =null;
    }

    //添加一个节点
    public void add(Emp emp){
        if(head==null){     //当前链表为空
            //直接添加到head
            head=emp;
        }else {
            //创建一个指针
            Emp temp=head;
            //将temp指向到最后
            while (temp.next!=null){
                temp=temp.next;
            }
            //将节点添加到最后
            temp.next=emp;
        }
    }

    //根据id查找一个员工
    public Emp findById(int id){
        if(head==null){     //链表为空
            return null;
        }else {
            //创建一个辅助指针
            Emp temp=head;
            while (temp!=null){
                if(temp.id==id){    //找到了就返回这个员工
                    return temp;
                }else {
                    temp=temp.next;
                }
            }
            //没有找到这个id返回null
            return null;
        }
    }

    //删除一个员工
    public void removeById(int id){
        if(head!=null){ //链表不为空
            if(head.id==id){    //要删除的是第一个元素
                if(head.next==null){    //链表中只有一个元素
                    head=null;
                }else{      //链表中有多个元素
                    head=head.next;
                }
            }else {
                //定义一个辅助指针
                Emp temp=head;
                while(temp.next!=null){
                    if(temp.next.id==id){
                        //删除temp后面的元素
                        temp.next=temp.next.next;
                        return;
                    }
                    //后移
                    temp=temp.next;
                }
            }
        }
    }

    //遍历链表
    public void print(int i){
        if(head==null){ //当前链表为空
            System.out.println("第"+i+"条链表为空");
        }else{
            System.out.print("第"+i+"条链表为:");
            //创建一个辅助指针
            Emp temp=head;
            while(temp!=null){
                System.out.print(temp+"\t");
                temp=temp.next;
            }
            System.out.println();
        }
    }
}

//员工类
class Emp{
    public int id;
    public String name;
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
        this.next=null;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

//测试
class Test{
    public static void main(String[] args) {
        //创建哈希表
        HashTable hashTable=new HashTable(7);
        hashTable.add(new Emp(1,"tom"));
        hashTable.add(new Emp(8,"jack"));
        hashTable.add(new Emp(2,"smith"));
        hashTable.add(new Emp(4,"mike"));
        hashTable.print();
        System.out.println("---------------------");
        Emp emp=hashTable.findById(4);
        System.out.println(emp);
        System.out.println("---------------------");
//        arithmetic1.hashTable.removeById(4);
//        arithmetic1.hashTable.removeById(8);
        hashTable.removeById(1);
        hashTable.print();
    }
}
